'''
2维树状数组，
单点插入
区间查询
'''


class IndexTree():
    def __init__(self, m, n):
        self.tree = [[0] * (m + 1) for _ in range(n + 1)]
        self.m = m
        self.n = n

    def add(self, i, j, v):
        x, y = i, j
        while x <= self.m:
            y = j
            while y <= self.n:
                self.tree[x][y] += v
                y += y & -y
            x += x & -x

    # 左上点(1,1) 到 右下点(i,j)； 这个矩阵范围内的累加和
    def _sum(self, i, j):
        res = 0
        x, y = i, j
        while x > 0:
            y = j
            while y > 0:
                res += self.tree[x][y]
                y -= y & -y
            x -= x & -x
        return res

    # 左上点(r1,c1) 到 右下点(r2,c2)； 这个矩阵范围内的累加和
    def sum_region(self, r1, c1, r2, c2):
        return self._sum(r2, c2) - self._sum(r1 - 1, c2) - self._sum(r2, c1 - 1) + self._sum(r1 - 1, c1 - 1)
